/*

Date:20210505 15:45PM
key:打家劫舍！！选了nums[i]就不能选相邻的元素，那么将他们排序后，就不能连着选！
    将存储结构为 数字 出现次数 放入map自动排序，再放到vector做dp。
    这里是通过检查相邻的v[i].first是否相差1，如果是则满足打家劫舍，不是则直接加，
    特别注意第二个初始化同样检查是否连续。
    只不过这次每个nums[i]的价值要乘出现次数
*/

class Solution {
public:

    int deleteAndEarn(vector<int>& nums) 
    {
        //放进map方便排序和统计出现次数
        map<int,int>m;
        for(int i:nums)
        {
            if(m.find(i)==m.end())
            {
                m.insert(pair<int,int>(i,1));
            }
            else
            {
                m.find(i)->second++;
            }
        }

        //放进vector方便dp
        vector<pair<int,int>>v;
        for(pair<int,int>p:m)
        {
            v.push_back(pair<int,int>(p.first,p.second));
            
        }
        int*dp=new int[v.size()];

        //0
        dp[0]=v[0].first*v[0].second;
        if(v.size()==1){return dp[0];}
        //1,第二个初始化也要考虑了
        if(v[1].first!=v[0].first+1)
        {
            dp[1]=dp[0]+(v[1].first*v[1].second);
        }
        else{dp[1]=max(dp[0],(v[1].first*v[1].second));}
        if(v.size()==2){return dp[1];}

        //dp
        for(int i=2;i<v.size();i++)
        {
            if(v[i].first==v[i-1].first+1)
            {
                dp[i]=max(dp[i-2]+(v[i].first*v[i].second),dp[i-1]);
            }
            else{dp[i]=dp[i-1]+(v[i].first*v[i].second);}
            //cout<<dp[i]<<" ";
        }
        return dp[v.size()-1];
    }
};